package linkedlist

import (
	"fmt"
	"strings"
)

type ListNode struct {
	next  *ListNode
	value interface{}
}

type LinkedList struct {
	head   *ListNode
	length uint
}

func NewListNode(v interface{}) *ListNode {
	return &ListNode{nil, v}
}

func (n *ListNode) GetNext() *ListNode {
	return n.next
}

func (n *ListNode) GetValue() interface{} {
	return n.value
}

func NewLinkedList() *LinkedList {
	return &LinkedList{NewListNode(0), 0}
}

// 在链表某个节点后面插入一个节点

func (l *LinkedList) InsertAfter(p *ListNode, v interface{}) bool {
	if p == nil {
		return false
	}
	newNode := NewListNode(v)
	oldNext := p.next
	p.next = newNode
	newNode.next = oldNext
	l.length++
	return true
}

// 在链表某一个节点前面插入一个节点

func (l *LinkedList) InsertBefore(p *ListNode, v interface{}) bool {
	if p == nil || p == l.head {
		return false
	}
	cur := l.head.next
	pre := l.head
	for cur != nil {
		if p == cur {
			break
		}
		pre = cur
		cur = cur.next
	}
	if cur == nil {
		return false
	}
	newNode := NewListNode(v)
	pre.next = newNode
	newNode.next = cur
	l.length++
	return true
}

// 插入一个节点到链表头部

func (l *LinkedList) InsertToHead(v interface{}) bool {
	return l.InsertAfter(l.head, v)
}

// 插入一个节点到链表尾部

func (l *LinkedList) InsertToTail(v interface{}) bool {
	cur := l.head
	for cur.next != nil {
		cur = cur.next
	}
	return l.InsertAfter(cur, v)
}

// 通过索引查找链表节点

func (l *LinkedList) FindByIndex(index uint) *ListNode {
	if index >= l.length {
		return nil
	}
	cur := l.head.next
	var i uint = 0
	for ; i < index; i++ {
		cur = cur.next
	}
	return cur
}

// 从链表删除节点，时间复杂度on

func (l *LinkedList) DeleteNode(p *ListNode) bool {
	if p == nil {
		return false
	}
	// p是head节点
	if p == l.head {
		l.head = l.head.next
		return true
	}
	cur := l.head.next
	pre := l.head
	for cur != nil {
		if cur == p {
			break
		}
		pre = cur
		cur = cur.next
	}
	if cur == nil {
		return false
	}
	pre.next = p.next
	p = nil
	l.length--
	return true
}

// 如果节点p一定存在于链表，那么删除一个节点时间复杂度可以是o1
// 把下一个节点的内容复制到需要删除的节点上覆盖原有的内容，再把下一个节点删除，就相当于删除了需要删除的节点

func (l *LinkedList) DeleteNodeMustExist(p *ListNode) bool {
	if l.head == nil {
		return false
	}
	if p == nil {
		return false
	}
	// 要删除的节点不是尾节点
	if p.next != nil {
		pNext := p.next
		p.value = pNext.value
		p.next = pNext.next
		pNext = nil
	} else if l.head == p { // 链表只有一个节点，删除头节点（也就是尾节点）
		l.head = nil
		p = nil
	} else { // 链表中有多个节点
		pNode := l.head
		for pNode.next != p {
			pNode = pNode.next
		}
		pNode.next = nil
		p = nil
	}
	return true
}

// 在一个排序的链表中，如何删除重复的链表节点

func (l *LinkedList) DeleteRepeatNode() {
	if l.head == nil {
		return
	}
	var pPreNode *ListNode
	var pNode = l.head
	for pNode != nil {
		pNext := pNode.next
		needDel := false
		if pNext != nil && pNext.value == pNode.value {
			needDel = true
		}
		if !needDel {
			pPreNode = pNode
			pNode = pNode.next
		} else {
			value := pNode.value
			pToBeDel := pNode
			for pToBeDel != nil && pToBeDel.value == value {
				pNext = pToBeDel.next
				pToBeDel = nil
				pToBeDel = pNext
			}
			if pPreNode == nil {
				l.head = pNext
			} else {
				pPreNode.next = pNext
			}
			pNode = pNext
		}
	}
}

// 反转链表

func (l *LinkedList) Reverse() {
	if nil == l.head {
		return
	}
	var pre *ListNode = nil
	cur := l.head.next
	for cur != nil {
		tmp := cur.next
		cur.next = pre
		pre = cur
		cur = tmp
	}
	l.head.next = pre
}

// 判断连接是否有环

func (l *LinkedList) HasCycle() bool {
	if l.head != nil {
		slow := l.head
		fast := l.head
		for fast != nil && fast.next != nil {
			slow = slow.next
			fast = fast.next.next
			if slow == fast {
				return true
			}
		}
	}
	return false
}

// 链表相加求和
//输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
//输出：7 -> 0 -> 8
//原因：342 + 465 = 807

func AddTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	ret := &ListNode{
		value: 0,
		next:  nil,
	}
	ca := 0
	current := ret
	for l1 != nil || l2 != nil {
		x, y := 0, 0
		if l1 != nil {
			x = l1.value.(int)
			l1 = l1.next
		}
		if l2 != nil {
			y = l2.value.(int)
			l2 = l2.next
		}
		sum := x + y + ca
		ca = sum / 10
		current.next = &ListNode{
			value: sum % 10,
			next:  nil,
		}
		current = current.next
	}
	if ca != 0 {
		current.next = &ListNode{
			value: ca,
			next:  nil,
		}
	}
	return ret.next
}

// 两个链表的第一个公共节点
// 先遍历其中一个链表并记录节点到map
// 然后遍历第二个链表，如果节点在map中存在说明相交了

func GetIntersectionNode(a, b *ListNode) *ListNode {
	// map 存储法 时间复杂度 o(m+n) 空间复杂度om
	vis := map[*ListNode]bool{}
	for tmp := a; tmp != nil; tmp = tmp.next {
		vis[tmp] = true
	}
	for tmp := b; tmp != nil; tmp = tmp.next {
		if vis[tmp] {
			return tmp
		}
	}
	return nil
}

// 双指针法
// 两个指针分别指向两个链表的头部
// 每次操作都需要同时更新pa pb，
// 如果pa不为空，则将指针pa移动到下一个节点；如果pb不为空，则将指针pb移动到下一个节点
// 如果pa为空，则将指针pa移动到链表b的头节点；如果pb为空，则将pb移动到链表a的头结点
// 当pa pb指向同一个节点或都为空时，返回它们指向的节点或null

func GetIntersectionNodeOfTwoPointer(a, b *ListNode) *ListNode {
	if a == nil || b == nil {
		return nil
	}
	pa, pb := a, b
	for pa != pb {
		if pa == nil {
			pa = b
		} else {
			pa = pa.next
		}
		if pb == nil {
			pb = a
		} else {
			pb = pb.next
		}
	}
	return pa
}

// 寻找相遇节点

func (l *LinkedList) MeetingNode() *ListNode {
	if l.head == nil {
		return nil
	}
	pSlow := l.head.next
	if pSlow == nil {
		return nil
	}
	pFast := pSlow.next
	for pFast != nil && pSlow != nil {
		if pFast == pSlow {
			return pFast
		}
		pSlow = pSlow.next
		pFast = pFast.next
		if pFast != nil {
			pFast = pFast.next
		}
	}
	return nil
}

// 链表中环的入口节点，在如下的链表中，环的入口节点是节点3
// 1 ->2 ->3-> 4-> 5-> 6
//          <----------<|

func (l *LinkedList) EntryNodeOfLoop() *ListNode {
	// 得到环中任意一个节点
	meetingNode := l.MeetingNode()
	if meetingNode == nil {
		return meetingNode
	}

	// 得到环中节点的数目
	var nodesInLoop = 1
	pNode1 := meetingNode
	for pNode1.next != meetingNode {
		pNode1 = pNode1.next
		nodesInLoop++
	}

	// 先移动pNode1 次数为环中节点的数目
	pNode1 = l.head
	for i := 0; i < nodesInLoop; i++ {
		pNode1 = pNode1.next
	}

	// 再移动pNode1和pNode2
	pNode2 := l.head
	for pNode1 != pNode2 {
		pNode1 = pNode1.next
		pNode2 = pNode2.next
	}

	return pNode1
}

// 合并两个有序链表

func MergeSortedList(l1, l2 *LinkedList) *LinkedList {
	if nil == l1 || nil == l1.head || nil == l1.head.next {
		return l2
	}
	if nil == l2 || nil == l2.head || nil == l2.head.next {
		return l1
	}
	// 新链表
	l := &LinkedList{head: &ListNode{}}
	cur := l.head

	curl1 := l1.head.next
	curl2 := l2.head.next
	for nil != curl1 && nil != curl2 {
		if curl1.value.(int) > curl2.value.(int) {
			cur.next = curl2
			curl2 = curl2.next
		} else {
			cur.next = curl1
			curl1 = curl1.next
		}
		cur = cur.next // 移动cur
	}

	// 处理cul1 cul2剩余没有合并的链表
	if nil != curl1 {
		cur.next = curl1
	} else if nil != curl2 {
		cur.next = curl2
	}

	return l
}

// 求链表倒数第N个节点
// 0---n
// slow ----   fast
// slow -->    fast--> 直到fast移动到最后一个节点，这时候slow节点距离head就是N

func (l *LinkedList) DeleteBottomN(n int) {
	if n <= 0 || l.head == nil || l.head.next == nil {
		return
	}
	fast := l.head
	for i := 0; i <= n && fast != nil; i++ {
		fast = fast.next
	}

	if fast == nil {
		return
	}
	slow := l.head
	for fast.next != nil {
		slow = slow.next
		fast = fast.next
	}
	slow.next = slow.next.next
}

/*
获取链表中间节点
*/
func (l *LinkedList) FindMiddleNode() *ListNode {
	if nil == l.head || nil == l.head.next {
		return nil
	}
	if nil == l.head.next.next {
		return l.head.next
	}

	slow, fast := l.head, l.head
	for nil != fast && nil != fast.next {
		slow = slow.next
		fast = fast.next.next
	}
	return slow
}

func (l *LinkedList) Print() {
	cur := l.head.next
	format := strings.Builder{}
	for cur != nil {
		format.WriteString(fmt.Sprintf("%+v", cur.GetValue()))
		cur = cur.next
		if cur != nil {
			format.WriteString("->")
		}
	}
	fmt.Println(format.String())
}
